package study.sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
//        int[] arr = {101, 34, -119, 1, 8, 99, -9, 67};
//        insertSort(arr);
        int[] arr = {101, 34, -119, 1};
        System.out.println("排序前：" + Arrays.toString(arr));
        insertSort3(arr);
    }

    /**
     * 推导过程
     * @param arr
     */
    public static void insertSort2(int[] arr){
        //{101, 34, -119, 1}




        //第1轮 {101, 34, -119, 1} => {34, 101, -119, 1}
        //定义待插入的数值
        int insertValue = arr[1];
        int insertIndex = 0;
        /**
         * 条件1：insertIndex >= 0，保证了数组不越界
         * 条件2：insertValue < arr[insertIndex]，待插入的值与插入位置的值比较
         * 第1轮：
         * insertValue = 34
         * arr[insertIndex] = arr[0] = 101
         */
        while (insertIndex >= 0 && insertValue < arr[insertIndex]){
            //往后移
            arr[insertIndex + 1] = arr[insertIndex];
            //此时数组为：{101, 101, -119, 1}
            insertIndex--;  //insertIndex = -1
        }
        //此时insertIndex = -1，insertValue = 34，即arr[0] = 34
        arr[insertIndex + 1] = insertValue;
        //此时数组为：{34, 101, -119, 1}
        System.out.println("第1轮排序后：" + Arrays.toString(arr));



        //第2轮 {34, 101, -119, 1} => {-119, 34, 101, 1}
        //定义待插入的数值
        insertValue = arr[2];
        insertIndex = 1;
        while (insertIndex >= 0 && insertValue < arr[insertIndex]){
            //往后移
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertValue;

        System.out.println("第2轮排序后：" + Arrays.toString(arr));



        //第3轮 {-119, 34, 101, 1} => {-119, 1, 34, 101}
        //定义待插入的数值
        insertValue = arr[3];
        insertIndex = 2;
        while (insertIndex >= 0 && insertValue < arr[insertIndex]){
            //往后移
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertValue;

        System.out.println("第3轮排序后：" + Arrays.toString(arr));

    }

    /**
     * 完善代码
     * @param arr
     */
    public static void insertSort3(int[] arr){

        int insertValue = 0;
        int insertIndex = 0;

        for (int i = 1; i < arr.length; i++) {
            //定义待插入的数值
            insertValue = arr[i];
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertValue < arr[insertIndex]){
                //往后移
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex + 1] = insertValue;
            System.out.println("第" + i + "轮排序后：" + Arrays.toString(arr));
        }

    }

    public static void insertSort(int[] arr){
        //arr = {101,| 34, 119, 1};

        //arr = {34, 101, | 119, 1};
        //arr = {34, 101, 119, | 1};
        //arr = {1，34, 101, 119};


        int i = 0;
        int temp = 0;

        for (int j = 1; j < arr.length; j++) {
            i = j - 1;
            temp = 0;
            while (i >= 0){
                if (arr[i+1] < arr[i]){
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
                i--;
            }
        }
        System.out.println("插入排序法：" + Arrays.toString(arr));


/*

        int i = 1 - 1;
        int temp = 0;
        while (i >= 0){
            if (arr[i+1] < arr[i]){
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
            i--;
        }
        System.out.println("第1轮排序：" + Arrays.toString(arr));


        //arr = {34, 101, | 119, 1};
        i = 2 - 1;
        temp = 0;
        while (i >= 0){
            if (arr[i+1] < arr[i]){
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
            i--;
        }
        System.out.println("第2轮排序：" + Arrays.toString(arr));


        //arr = {34, 101, 119, | 1};
        i = 3 - 1;
        temp = 0;
        while (i >= 0){
            if (arr[i+1] < arr[i]){
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
            i--;
        }
        System.out.println("第3轮排序：" + Arrays.toString(arr));

*/

    }
}
